package leetcode

/*
 * @lc app=leetcode.cn id=239 lang=golang
 *
 * [239] 滑动窗口最大值
 */

// @lc code=start
type deque struct {
	deque []int
	nums  []int
}

func (d *deque) push(i int) {
	for len(d.deque) > 0 && d.nums[d.deque[len(d.deque)-1]] <= d.nums[i] {
		d.deque = d.deque[:len(d.deque)-1]
	}
	d.deque = append(d.deque, i)
}

func maxSlidingWindow(nums []int, k int) []int {
	d := deque{nums: nums}
	for i := 0; i < k; i++ {
		d.push(i)
	}
	n := len(nums)
	ret := make([]int, 1, n-k+1)
	ret[0] = nums[d.deque[0]]
	for i := k; i < n; i++ {
		d.push(i)
		for i-d.deque[0] >= k {
			d.deque = d.deque[1:]
		}
		ret = append(ret, nums[d.deque[0]])
	}
	return ret
}

// @lc code=end
